package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-the-substring-with-maximum-cost/
 * @create 2025/8/29 16:44
 * @since JDK17
 */

public class Solution21 {
    public int maximumCostSubstring(String str, String chars, int[] vals) {
        char[] s1 = str.toCharArray(), s2 = chars.toCharArray();
        int[] h = new int[26], dp = new int[s1.length];
        Arrays.fill(h, Integer.MIN_VALUE);
        for (int i = 0; i < s2.length; i++) {
            h[s2[i] - 'a'] = vals[i];

        }
        for (int i = 0; i < 26; i++) {
            if (h[i] == Integer.MIN_VALUE) {
                h[i] = i + 1;
            }
        }
        dp[0] = h[s1[0] - 'a'];
        int ans = Math.max(dp[0], 0);
        for (int i = 1; i < s1.length; i++) {
            dp[i] = h[s1[i] - 'a'] + Math.max(dp[i - 1], 0);
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
}
